You made a bet
with your friend that he would not hit the target after making n shots. The probability that your friend
hits the target with a single shot is a percent.
Find the maximum
number of shots n for which it makes sense for you to place the bet. The bet is considered
reasonable if the probability that your friend hits the target with at least
one of the shots is strictly less than 50%.
Input. Each line contains a
single integer a (1 ≤ a ≤ 100) – the probability that your friend hits the
target with one shot.
Output. For each test, print on a
separate line the maximum number of shots for which it makes sense for you to
place the bet.
|
Sample input |
Sample
output |
|
40 20 50 1 |
1 3 0 68 |
SOLUTION
probability
Algorithm analysis
The probability that your
friend hits the target with a single shot is
p = a / 100
Then the probability that
he does not hit the target with one shot is
1 – p = 1 – a
/ 100
Since all shots are
independent, the probability that your friend does not hit the target even once
after making n shots is equal to
(1 – a / 100.0)n
The probability that your
friend hits the target at least once in n shots is the complement of
this event:
1 – (1 – a / 100.0)n
According to the problem
statement, the bet makes sense if the probability of at least one hit is
strictly less than 50%, that is:
1 – (1 – a / 100.0)n < 0.5
Let us transform this
inequality:
(1 – a / 100.0)n > 0.5
Thus, it is required to
find the maximum integer value of n for which this inequality holds. As
soon as n increases to the point where the probability of missing the
target in all shots becomes less than or equal to 0.5, the bet ceases to be
worthwhile.
Algorithm implementation
Read the input value of the probability a.
while (scanf("%d", &a) == 1)
{
The probability of missing the target is computed and stored in the
variable miss.
miss = 1
- a / 100.0;
The variable p stores the value of the probability (1 – a / 100.0)n.
p = miss;
n = 0;
We look for the largest value of n for which (1 – a / 100.0)n > 0.5.
while (p > 0.5)
{
n++;
p *=
miss;
}
Print the answer.
printf("%d\n", n);
}